from collections import deque
from typing import List


class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        trees = []
        for i in range(len(forest)):
            for j in range(len(forest[0])):
                if forest[i][j] > 1:
                    trees.append((forest[i][j], i, j))
        trees.sort()
        start = (0, 0)
        ans = 0
        for tree in trees:
            step = self.bfs(forest, start, (tree[1], tree[2]))
            if step == -1:
                return -1
            ans += step
            start = (tree[1], tree[2])
        return ans
            

    def bfs(self, forest, start, to):
        if start == to:
            return 0
        queue = deque([start])
        visited = set()
        visited.add(start)
        step = 0
        while queue:
            step += 1
            sz = len(queue)
            for i in range(sz):
                x, y = queue.popleft()
                for i, j in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= i < len(forest) and 0 <= j < len(forest[0]) and forest[i][j] > 0:
                        if (i, j) == to:
                            return step
                        if (i, j) not in visited and forest[i][j] != 0:
                            queue.append((i, j))
                            visited.add((i, j))
        return -1
        